package com.demo.datastructure.hashTable;

import java.util.HashMap;

/**
 * @description:
 * @author: ljr
 * @time: 2021/5/22 18:38
 */
public class LruHashTable<K,V> {

    private final static Integer DEFAULT_CAPACITY= 10;

    private final DNode<K,V> headerNode;

    private final DNode<K,V> tailNode;

    /**
     * 链表长度
     */
    private Integer length;

    /**
     * 链表容量
     */
    private final Integer capacity;

    /**
     * 散列表存储key
     */
    private final HashMap<K, DNode<K, V>> table;


    public LruHashTable(int capacity){
        this.length = 0;
        this.capacity = capacity;
        headerNode = new DNode<>();
        tailNode = new DNode<>();
        headerNode.next = tailNode;
        tailNode.prev = headerNode;
        table = new HashMap<>();
    }


    public LruHashTable(){
        this(DEFAULT_CAPACITY);
    }


    public void add(K key, V value){
        DNode<K, V> node = table.get(key);
        if(node == null){
            node = new DNode<>(key,value);
            table.put(key, node);
            addNode(node);
            if(++length > capacity){
                DNode<K, V> tail = popTail();
                table.remove(tail.key);
                length--;
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }

    private void moveToHead(DNode<K,V> node) {
        removeNode(node);
        addNode(node);
    }

    private DNode<K,V> popTail() {
        DNode oldPrev = tailNode.prev;
        removeNode(oldPrev);
        return oldPrev;
    }

    private void removeNode(DNode oldNode) {
        if(oldNode == headerNode){
            return;
        }
        oldNode.prev.next =  oldNode.next;
        oldNode.next.prev =  oldNode.prev;
    }

    private void addNode(DNode<K,V> node) {
        node.next = headerNode.next;
        node.prev = headerNode;
        node.next.prev = node;
        headerNode.next = node;
    }

    public V get(K key){
        DNode node = table.get(key);
        if(node == null){
            return null;
        }
        moveToHead(node);
        return (V) node.value;
    }


    public void remove(K key){
        DNode node = table.get(key);
        if(node == null){
            return;
        }
        length--;
        table.remove(key);
        removeNode(node);
    }

    private static class DNode<K,V>{
        private K key;

        private V value;

        private DNode<K,V> prev;

        private DNode<K,V> next;

        public DNode() { }

        public DNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
